package lc207;

import java.util.*;

public class Lc207_1 {

    /**
     * 1.生成邻接表
     * 2.生成拓扑序列(修课程)
     * 3.判断课程是否可以修完
     * time：O(n+m) n为课程数(prerequisites.size) m为先修课程的要求数量(numCourses)
     * space: O(n+m)
     * spend: 60m 了解拓扑序列，理解题目，研究解法
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 生成邻接表
        // 存储每个课程的限制数，下标0为课程id，下标1为限制总数，默认都是0
        int[] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> graph = new HashMap<>(numCourses * 2);  // 邻接表存储(ListMap都行)
        for(int i = 0; i < numCourses; i++){
            graph.put(i, new ArrayList<>());
        }
        // 先生成邻接表
        for(int[] prerequisite: prerequisites){
            int courseId = prerequisite[0];         // 当前课程id
            inDegree[courseId]++;                   // 先将课程的限制总数+1
            int preCourseId = prerequisite[1];      // 前置课程id
            graph.get(preCourseId).add(courseId);   // 从邻接表中添加限制课程的前置课程id
        }
        // 2.生成拓扑序列(也可以理解为课程不断的被完成)
        // 2.1 初始化拓扑序列(先将课程限制为0的装入队列)
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                queue.add(i);
            }
        }
        // 2.2 处理课程限制为0的课程的下一个序列(开始进修课)
        while(!queue.isEmpty()){
            int cur = queue.poll();
            // 先从当前课程中获取它的序列
            List<Integer> toTake = graph.get(cur);
            for(int i = 0; toTake != null && i < toTake.size(); i++){
                inDegree[toTake.get(i)]--;// 进修完，限制课程数-1
                // 当限制课程数=0，则进修下一个课程
                if(inDegree[toTake.get(i)] == 0){
                    queue.add(toTake.get(i));
                }
            }
        }
        // 3. 进修完课程后，如果还有课程存在课程限制数，而说明课程修不完，否则修完
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] != 0){
                return false;
            }
        }
        return true;
    }

}
